{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Distinct Roll Sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distinctSequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同骰子序列的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;。你需要掷一个 6 面的骰子&nbsp;<code>n</code>&nbsp;次。请你在满足以下要求的前提下，求出 <strong>不同</strong>&nbsp;骰子序列的数目：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>序列中任意 <strong>相邻</strong>&nbsp;数字的 <strong>最大公约数</strong>&nbsp;为 <code>1</code>&nbsp;。</li>\n",
    "\t<li>序列中 <strong>相等</strong>&nbsp;的值之间，至少有 <code>2</code>&nbsp;个其他值的数字。正式地，如果第&nbsp;<code>i</code>&nbsp;次掷骰子的值 <strong>等于</strong>&nbsp;第&nbsp;<code>j</code>&nbsp;次的值，那么&nbsp;<code>abs(i - j) &gt; 2</code>&nbsp;。</li>\n",
    "</ol>\n",
    "\n",
    "<p>请你返回不同序列的 <strong>总数目</strong>&nbsp;。由于答案可能很大，请你将答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>如果两个序列中至少有一个元素不同，那么它们被视为不同的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4\n",
    "<b>输出：</b>184\n",
    "<b>解释：</b>一些可行的序列为 (1, 2, 3, 4) ，(6, 1, 2, 3) ，(1, 2, 3, 1) 等等。\n",
    "一些不可行的序列为 (1, 2, 1, 3) ，(1, 2, 3, 6) 。\n",
    "(1, 2, 1, 3) 是不可行的，因为第一个和第三个骰子值相等且 abs(1 - 3) = 2 （下标从 1 开始表示）。\n",
    "(1, 2, 3, 6) i是不可行的，因为 3 和 6 的最大公约数是 3 。\n",
    "总共有 184 个不同的可行序列，所以我们返回 184 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 2\n",
    "<b>输出：</b>22\n",
    "<b>解释：</b>一些可行的序列为 (1, 2) ，(2, 1) ，(3, 2) 。\n",
    "一些不可行的序列为 (3, 6) ，(2, 4) ，因为最大公约数不为 1 。\n",
    "总共有 22 个不同的可行序列，所以我们返回 22 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-distinct-roll-sequences](https://leetcode.cn/problems/number-of-distinct-roll-sequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-distinct-roll-sequences](https://leetcode.cn/problems/number-of-distinct-roll-sequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        dic = {c: 1 for c in '123456'}\n",
    "        for _ in range(n - 1):\n",
    "            dic = step(dic)\n",
    "            #print(sum(dic.values()) % 1000000007)\n",
    "        return sum(dic.values()) % (10**9+7)\n",
    "\n",
    "dic_next = {'1': '23456', '2': '135', '3': '1245', '4': '135', '5': '12346', '6': '15'}\n",
    "\n",
    "def step(dic):\n",
    "    dic2 = defaultdict(int)\n",
    "\n",
    "    for k, v in dic.items():\n",
    "        finger = dic_next[k[-1]]\n",
    "        for ch in finger:\n",
    "            if ch in k:\n",
    "                continue\n",
    "            k2 = (k + ch)[-2:]\n",
    "            dic2[k2] = (dic2[k2] + v) % (10**9+7)\n",
    "    #print('dic2', dic2)\n",
    "    return dic2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        M = 10**9+7\n",
    "        links = [\n",
    "            None,\n",
    "            [2,3,4,5,6],\n",
    "            [1,3,5],\n",
    "            [1,2,4,5],\n",
    "            [1,3,5],\n",
    "            [1,2,3,4,6],\n",
    "            [1,5]\n",
    "        ]\n",
    "        lastSum = [1]*7\n",
    "        lastSum[0] = 0\n",
    "        lastSum1 = [0]*7 \n",
    "        states = [[0]*7 for _ in range(7)]\n",
    "        states1 = [[0]*7 for _ in range(7)]\n",
    "        for r in range(n-1):\n",
    "            for num in range(1, 7):\n",
    "                lastSum1[num] = 0\n",
    "                for off in range(1, 7):\n",
    "                    states1[num][off] = 0\n",
    "                for lastNum in links[num]:\n",
    "                    v = sum(states[lastNum][r] for r in links[lastNum] if r != num) if r > 0 else lastSum[lastNum]\n",
    "                    states1[num][lastNum] = v % M\n",
    "                    lastSum1[num] = (lastSum1[num] + v) % M\n",
    "            states, states1 = states1, states\n",
    "            lastSum, lastSum1 = lastSum1, lastSum\n",
    "        return sum(lastSum) % M\n",
    "\n",
    "        \n",
    "        \n",
    "        # R[k][n][m] = R[k-1][m][r]\n",
    "        # 1: 2-6\n",
    "        # 2: 1 3 5\n",
    "        # 3: 1 2 4 5\n",
    "        # 4: 1 3 5\n",
    "        # 5: 1 2 3 4 6\n",
    "        # 6: 1 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 6*6*6=216, 7*7*6=294\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        dic = {c: 1 for c in '123456'}\n",
    "        for i in range(n - 1):\n",
    "            dic = step(dic)\n",
    "            #print(sum(dic.values()) % 1000000007)\n",
    "        return sum(dic.values()) % 1000000007\n",
    "\n",
    "\n",
    "dic_next = {'1': '23456', '2': '135', '3': '1245', '4': '135', '5': '12346', '6': '15'}\n",
    "\n",
    "\n",
    "def step(dic):\n",
    "    dic2 = defaultdict(int)\n",
    "\n",
    "    for k, v in dic.items():\n",
    "        finger = dic_next[k[-1]]\n",
    "        for ch in finger:\n",
    "            if ch in k:\n",
    "                continue\n",
    "            k2 = (k + ch)[-2:]\n",
    "            dic2[k2] = (dic2[k2] + v) % 1000000007\n",
    "    #print('dic2', dic2)\n",
    "    return dic2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if(n==1):return 6\n",
    "        if(n==2):return 22\n",
    "        f,mod=[4,2,2,4,2,2,2,2,2],1000000007\n",
    "        # 12 13 16 21 23 31 32 61 15\n",
    "        # 14 53 56 25 43 35 34 65 51\n",
    "        # 52       41\n",
    "        # 54       45\n",
    "        for i in range(3,n+1):\n",
    "            f=[\\\n",
    "            (f[3]+2*f[5]+2*f[7]+2*f[8])%mod,\\\n",
    "            (f[3]+f[7]+f[8])%mod,\\\n",
    "            (f[3]+f[5]+f[8])%mod,\\\n",
    "            (f[0]+2*f[6])%mod,\\\n",
    "            f[0],\\\n",
    "            (f[1]+2*f[4])%mod,\\\n",
    "            (f[1]*2+f[4])%mod,\\\n",
    "            f[2],\\\n",
    "            (f[3]+f[5]+f[7])%mod]\n",
    "            # f[i][1]=(f[i-1][3]+f[i-1][7]+f[i-1][8])%mod\n",
    "            # f[i][2]=(f[i-1][3]+f[i-1][5]+f[i-1][8])%mod\n",
    "            # f[i][3]=(f[i-1][0]+2*f[i-1][6])%mod\n",
    "            # f[i][4]=f[i-1][0]\n",
    "            # f[i][5]=(f[i-1][1]+2*f[i-1][4])%mod\n",
    "            # f[i][6]=(f[i-1][1]*2+f[i-1][4])%mod\n",
    "            # f[i][7]=f[i-1][2]\n",
    "            # f[i][8]=(f[i-1][3]+f[i-1][5]+f[i-1][7])%mod\n",
    "        return sum(f)%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        # 1: 2 3 4 5 6\n",
    "        # 2: 1 3 5\n",
    "        # 3: 1 2 4 5\n",
    "        # 4: 1 3 5\n",
    "        # 5: 1 2 3 4 6\n",
    "        # 6: 1 5\n",
    "\n",
    "        if n==1:\n",
    "            return 6\n",
    "\n",
    "        mod = 10**9+7\n",
    "\n",
    "        trans = ((2,3,4,5,6),(1,3,5),(1,2,4,5),(1,3,5),(1,2,3,4,6),(1,5))\n",
    "\n",
    "        dp = [[0,1,1,1,1,1],[1,0,1,0,1,0],[1,1,0,1,1,0],[1,0,1,0,1,0],[1,1,1,1,0,1],[1,0,0,0,1,0]]\n",
    "        for _ in range(n-2):\n",
    "            newdp = [[0 for _ in range(6)] for _ in range(6)]\n",
    "            for i in range(6):\n",
    "                for j in trans[i]:\n",
    "                    newdp[i][j-1] = sum(dp[j-1][k-1] for k in trans[j-1] if k-1!=i)%mod\n",
    "            dp = newdp\n",
    "\n",
    "        res = 0\n",
    "        for i in dp:\n",
    "            res = (res+sum(i))%mod\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        constraints = {\n",
    "            1 : [2, 3, 4, 5, 6],\n",
    "            2 : [1, 3, 5],\n",
    "            3 : [1, 2, 4, 5],\n",
    "            4 : [1, 3, 5],\n",
    "            5 : [1, 2, 3, 4, 6],\n",
    "            6 : [1, 5]\n",
    "        }\n",
    "\n",
    "        second = [1] * 6\n",
    "        first = [len(constraints[key]) for key in range(1, 7)]\n",
    "\n",
    "        if n == 1:\n",
    "            return 6\n",
    "        elif n == 2:\n",
    "            return sum(first)\n",
    "        \n",
    "        for i in range(3, n + 1):\n",
    "            t = []\n",
    "            for x in range(1, 7):\n",
    "                cur = 0\n",
    "                for first_val in constraints[x]:\n",
    "                    cur += first[first_val - 1]\n",
    "                    if x in constraints[first_val]:\n",
    "                        cur -= second[x - 1]\n",
    "                if i > 3:\n",
    "                    cur += second[x - 1]\n",
    "                t.append((cur + MOD) % MOD)\n",
    "            first, second = t, first\n",
    "        \n",
    "        return sum(first) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if n == 1: return 6\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp1 = [[0] * 7 for _ in range(7)]  # dp[i][j]  # 表示前一次掷出j，再前一次掷出i的总数\n",
    "        dp2 = [[0] * 7 for _ in range(7)]\n",
    "        pre = [[], {2, 3, 4, 5, 6}, {1, 3, 5}, {1, 2, 4, 5}, {1, 3, 5}, {1, 2, 3, 4, 6}, {1, 5}]  # 一个数字前面允许的数字\n",
    "\n",
    "        for j in range(1, 7):\n",
    "            for i in pre[j]:\n",
    "                dp1[i][j] = 1\n",
    "\n",
    "        for _ in range(n - 2):\n",
    "            for i in range(1, 7):\n",
    "                for j in range(1, 7):\n",
    "                    dp2[i][j] = sum(dp1[x][i] for x in pre[i] if x != j and i != j and i in pre[j]) % MOD\n",
    "            dp1, dp2 = dp2, [[0] * 7 for _ in range(7)]\n",
    "        return sum(sum(x) for x in dp1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        # 初始化字典dic，每个数字初始出现1次\n",
    "        dic = {c: 1 for c in '123456'}\n",
    "        \n",
    "        # 根据序列长度循环更新字典\n",
    "        for _ in range(n - 1):\n",
    "            dic = step(dic)\n",
    "            #print(sum(dic.values()) % 1000000007)\n",
    "        \n",
    "        # 返回所有序列数量之和对1000000007取余的结果\n",
    "        return sum(dic.values()) % 1000000007\n",
    "\n",
    "# 用于存储每个数字对应的下一轮可能出现的数字\n",
    "dic_next = {'1': '23456', '2': '135', '3': '1245', '4': '135', '5': '12346', '6': '15'}\n",
    "\n",
    "def step(dic):\n",
    "    # 默认字典，用于存储下一轮的键值对\n",
    "    dic2 = defaultdict(int)\n",
    "\n",
    "    # 遍历当前字典的键值对\n",
    "    for k, v in dic.items():\n",
    "        # 获取当前数字k对应的下一轮可能出现的数字\n",
    "        finger = dic_next[k[-1]]\n",
    "        \n",
    "        # 遍历下一轮可能出现的数字\n",
    "        for ch in finger:\n",
    "            # 如果数字ch已经在当前序列中出现过，则跳过\n",
    "            if ch in k:\n",
    "                continue\n",
    "            \n",
    "            # 生成新的键k2，即在当前序列后添加数字ch\n",
    "            k2 = (k + ch)[-2:]\n",
    "            \n",
    "            # 将当前序列对应的值v累加到新键k2对应的值上，并对1000000007取余\n",
    "            dic2[k2] = (dic2[k2] + v) % 1000000007\n",
    "    \n",
    "    # 返回下一轮的字典\n",
    "    return dic2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dic_next = {'1': '23456', '2': '135', '3': '1245', '4': '135', '5': '12346', '6': '15'}\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        dic={c:1 for c in '123456'}\n",
    "        for _ in range(n-1):\n",
    "            dic=step(dic)\n",
    "        return sum(dic.values())%1000000007\n",
    "\n",
    "\n",
    "def step(dic):\n",
    "    dic2=defaultdict(int)\n",
    "    for k,v in dic.items():\n",
    "        fingeer=dic_next[k[-1]]\n",
    "        for ch in fingeer:\n",
    "            if ch in k:\n",
    "                continue\n",
    "            k2=(k+ch)[-2:]\n",
    "            dic2[k2]=(v+dic2[k2])%1000000007\n",
    "    return dic2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dic_next = {'1': '23456', '2': '135', '3': '1245', '4': '135', '5': '12346', '6': '15'}\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        dic={c:1 for c in '123456'}\n",
    "        for _ in range(n-1):\n",
    "            dic=step(dic)\n",
    "        return sum(dic.values())%1000000007\n",
    "\n",
    "\n",
    "def step(dic):\n",
    "    dic2=defaultdict(int)\n",
    "    for k,v in dic.items():\n",
    "        fingeer=dic_next[k[-1]]\n",
    "        for ch in fingeer:\n",
    "            if ch in k:\n",
    "                continue\n",
    "            k2=(k+ch)[-2:]\n",
    "            dic2[k2]=(v+dic2[k2])%1000000007\n",
    "    return dic2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "\n",
    "state = Counter()\n",
    "for i in range(1, 7):\n",
    "    for j in range(1, 7):\n",
    "        if gcd(i, j) == 1 and i != j:\n",
    "            state[i, j] = 1\n",
    "        \n",
    "transfer = defaultdict(set)\n",
    "for k1 in state:\n",
    "    for k2 in state:\n",
    "        if k1[1] == k2[0] and k1[0] != k2[1]:\n",
    "            transfer[k1].add(k2)\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 6\n",
    "        elif n == 2:\n",
    "            return 22\n",
    "        \n",
    "        d = state.copy()\n",
    "\n",
    "\n",
    "        for i in range(2, n):\n",
    "            pre = d.copy()\n",
    "            d.clear()\n",
    "            for k1 in pre:\n",
    "                for k2 in transfer[k1]:\n",
    "                    d[k2] += pre[k1]\n",
    "                    d[k2] %= mod\n",
    "\n",
    "\n",
    "        return sum(d.values()) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if n==1: return 6\n",
    "        dp = [[0]*6 for _ in range(6)]\n",
    "        for i in range(6):\n",
    "            for j in range(6):\n",
    "                dp[i][j] = (1 if math.gcd(i+1,j+1)==1 and i!=j else 0)\n",
    "        for x in range(2,n):\n",
    "            tmp = dp[:]\n",
    "            dp = [[0]*6 for _ in range(6)]\n",
    "            for i in range(6):\n",
    "                for j in range(6):\n",
    "                    for k in range(6):\n",
    "                        if math.gcd(i+1,j+1)==1 and i!=j and i!=k:\n",
    "                            dp[i][j] = (dp[i][j] + tmp[j][k])%MOD\n",
    "            pass\n",
    "        return sum([sum(e) for e in dp])%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        max_limit = 1000000000 + 7\n",
    "        # 特殊情况\n",
    "        if n == 1:\n",
    "            return 6\n",
    "        if n == 2:\n",
    "            return 22\n",
    "        possible_next = {\n",
    "            1: [2, 3, 4, 5, 6],\n",
    "            2: [1, 3, 5],\n",
    "            3: [1, 2, 4, 5],\n",
    "            4: [1, 3, 5],\n",
    "            5: [1, 2, 3, 4, 6],\n",
    "            6: [1, 5]\n",
    "        }\n",
    "        possible_next2 = dict()\n",
    "        for i in range(1, 7):\n",
    "            n2_dict = dict()\n",
    "            possible_next2[i] = n2_dict\n",
    "            for j in possible_next[i]:\n",
    "                n2_dict[j] = possible_next[j].copy()\n",
    "                n2_dict[j].remove(i)\n",
    "                pass\n",
    "            pass\n",
    "        # 此时 possible_next2[i][j] = [x, x, x, x]\n",
    "        # 构造一个方便遍历的 list\n",
    "        literal_seq = []\n",
    "        for i in range(1, 7):\n",
    "            for j in possible_next[i]:\n",
    "                literal_seq.append((i, j))\n",
    "                pass\n",
    "            pass\n",
    "\n",
    "        count = list()\n",
    "        count2 = list()\n",
    "        for i in range(7):\n",
    "            count.append([0] * 7)\n",
    "            count2.append([0] * 7)\n",
    "            pass\n",
    "\n",
    "        # 初始值\n",
    "        for (i, j) in literal_seq:\n",
    "            count[i][j] = len(possible_next2[i][j])\n",
    "            count2[i][j] = len(possible_next2[i][j])\n",
    "            pass\n",
    "\n",
    "        # 进行计算\n",
    "        for t in range(3, n):\n",
    "            for (i, j) in literal_seq:\n",
    "                count2[i][j] = 0\n",
    "                for k in possible_next2[i][j]:\n",
    "                    count2[i][j] += count[j][k]\n",
    "                    count2[i][j] %= max_limit\n",
    "                    pass\n",
    "                pass\n",
    "            tmp_count = count\n",
    "            count = count2\n",
    "            count2 = tmp_count\n",
    "            pass\n",
    "        res = 0\n",
    "        for (i, j) in literal_seq:\n",
    "            res += count[i][j]\n",
    "            res %= max_limit\n",
    "            pass\n",
    "        return res\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    print(s.distinctSequences(4))  # 184\n",
    "    print(s.distinctSequences(3))  # 66\n",
    "    print(s.distinctSequences(2))  # 22\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if n == 1: return 6\n",
    "        MOD = 10 ** 9 + 7\n",
    "        prev = [[0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0],\n",
    "                [1, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 0],\n",
    "                [1, 1, 1, 1, 0, 1], [1, 0, 0, 0, 1, 0]]\n",
    "        for i in range(2, n):\n",
    "            curr = [[0 for _ in range(6)] for _ in range(6)]\n",
    "            for l in range(6):\n",
    "                for k in range(6):\n",
    "                    for j in range(6):\n",
    "                        if j != l and k != l and gcd(k + 1, l + 1) == 1:\n",
    "                            curr[k][l] += prev[j][k]\n",
    "                curr[k][l] %= MOD\n",
    "            prev = curr\n",
    "        return sum(sum(row) for row in prev) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 6\n",
    "        cnt=None\n",
    "        for i in range(1,n):\n",
    "            ccnt=[[0 for _ in range(7)] for _ in range(7)]\n",
    "            if i==1:\n",
    "                for j in range(1,7):\n",
    "                    for k in range(1,7):\n",
    "                        if j!=k and gcd(j,k)==1:\n",
    "                            ccnt[k][j]=1\n",
    "            else:\n",
    "                for j in range(1,7):\n",
    "                    if j!=1:\n",
    "                        ccnt[1][j]=sum([cnt[j][k] for k in range(1,7) if k!=1])\n",
    "                    if j!=2 and gcd(j,2)==1:\n",
    "                        ccnt[2][j]=sum([cnt[j][k] for k in range(1,7) if k!=2])\n",
    "                    if j!=3 and gcd(j,3)==1:\n",
    "                        ccnt[3][j]=sum([cnt[j][k] for k in range(1,7) if k!=3])\n",
    "                    if j!=4 and gcd(j,4)==1:\n",
    "                        ccnt[4][j]=sum([cnt[j][k] for k in range(1,7) if k!=4])\n",
    "                    if j!=5 and gcd(j,5)==1:\n",
    "                        ccnt[5][j]=sum([cnt[j][k] for k in range(1,7) if k!=5])\n",
    "                    if j!=6 and gcd(j,6)==1:\n",
    "                        ccnt[6][j]=sum([cnt[j][k] for k in range(1,7) if k!=6])\n",
    "            cnt=ccnt\n",
    "        return sum([sum(cnt[i]) for i in range(7)])%(10**9+7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\r\n",
    "f = [[0] * 6 for _ in range(MX + 1)]\r\n",
    "f[1] = [1] * 6\r\n",
    "for i in range(2, MX):\r\n",
    "    for j in range(6):\r\n",
    "        for k in range(6):\r\n",
    "            if k != j and gcd(k + 1, j + 1) == 1:\r\n",
    "                f[i][j] += f[i - 1][k] - f[i - 2][j]\r\n",
    "        if i > 3: f[i][j] += f[i - 2][j]\r\n",
    "        f[i][j] %= MOD\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def distinctSequences(self, n: int) -> int:\r\n",
    "        return sum(f[n]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        MOD= 10 ** 9 + 7\n",
    "        f = [[0] * 6 for _ in range(n+1)]\n",
    "        f[1] = [1] * 6\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(6):\n",
    "                for k in range(6):\n",
    "                    if k != j and gcd(k + 1, j + 1) == 1:\n",
    "                        f[i][j] += f[i - 1][k] - f[i - 2][j]\n",
    "                if i > 3: f[i][j] += f[i - 2][j]\n",
    "                f[i][j] %= MOD\n",
    "        return sum(f[n]) % MOD\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\r\n",
    "f = [[0] * 6 for _ in range(MX + 1)]\r\n",
    "f[1] = [1] * 6\r\n",
    "for i in range(2, MX):\r\n",
    "    for j in range(6):\r\n",
    "        f[i][j] = (sum(f[i - 1][k] for k in range(6) if k != j and gcd(k + 1, j + 1) == 1)\r\n",
    "                   - (f[2][j] - (i > 3)) * f[i - 2][j]) % MOD\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def distinctSequences(self, n: int) -> int:\r\n",
    "        return sum(f[n]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i][j] := after i + 1 rolls, valid number of roll sequences end as j + 1\r\n",
    "# dp[0][j] = 1\r\n",
    "# dp[i][j] = sum(dp[i - 1][k], gcd(j + 1, k + 1) == 1)\r\n",
    "#   - dp[i - 2][j] * count of (k, gcd(j + 1, k + 1) == 1) if i > 1\r\n",
    "#   + dp[i - 2][j] if i > 2\r\n",
    "\r\n",
    "# 1 -> 2, 3, 4, 5, 6\r\n",
    "# 2 -> 1, 3, 5\r\n",
    "# 3 -> 1, 2, 4, 5\r\n",
    "# 4 -> 1, 3, 5\r\n",
    "# 5 -> 1, 2, 3, 4, 6\r\n",
    "# 6 -> 1, 5\r\n",
    "N = 0\r\n",
    "mod = 1000000007\r\n",
    "valid = [[1, 2, 3, 4, 5], [0, 2, 4], [0, 1, 3, 4], [0, 2, 4], [0, 1, 2, 3, 5], [0, 4]]\r\n",
    "dp = [[1] * 6 for _ in range(10000)]\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def distinctSequences(self, n: int) -> int:\r\n",
    "        global N\r\n",
    "        if n > N:\r\n",
    "            for i in range(1, n):\r\n",
    "                for j in range(6):\r\n",
    "                    dp[i][j] = sum(dp[i - 1][k] for k in valid[j]) % mod\r\n",
    "                    if i > 1:\r\n",
    "                        dp[i][j] = (mod + dp[i][j] - dp[i - 2][j] * len(valid[j]) % mod) % mod\r\n",
    "                    if i > 2:\r\n",
    "                        dp[i][j] = (dp[i][j] + dp[i - 2][j]) % mod\r\n",
    "            N = n\r\n",
    "        \r\n",
    "        return sum(dp[n - 1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        # 1. 递归, 序列枚举：定义f[i][last][last2]序列长度为i， 最后一个元素是last， 倒数第二个元素是last2的序列数目\n",
    "        # @cache\n",
    "        # def f(n:int, last:int, last2:int)-> int:\n",
    "        #     if n == 0: return 1\n",
    "        #     res = 0\n",
    "        #     for j in range(1, 7):\n",
    "        #         if j != last and j != last2 and gcd(j, last) == 1: # 判断互质，且相同元素间隔为2\n",
    "        #             res += f(n - 1, j, last)\n",
    "        #     return res % (10 ** 9 + 7)\n",
    "\n",
    "        # return f(n, 7, 7) # 7与[1,6]内的数字都不同且互质\n",
    "\n",
    "        # 2. 迭代：\n",
    "        MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "        f = [[0] * 6 for _ in range(MX + 1)]\n",
    "        f[1] = [1] * 6\n",
    "        for i in range(2, MX):\n",
    "            for j in range(6):\n",
    "                for k in range(6):\n",
    "                    if k != j and gcd(k + 1, j + 1) == 1:\n",
    "                        f[i][j] += f[i - 1][k] - f[i - 2][j]\n",
    "                if i > 3: f[i][j] += f[i - 2][j]\n",
    "                f[i][j] %= MOD\n",
    "        return sum(f[n]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        MOD, MX = 10 ** 9 + 7, 10 ** 4 + 1\n",
    "        f = [[0] * 6 for _ in range(MX + 1)]\n",
    "        f[1] = [1] * 6\n",
    "        for i in range(2, MX):\n",
    "            for j in range(6):\n",
    "                for k in range(6):\n",
    "                    if k != j and gcd(k + 1, j + 1) == 1:\n",
    "                        f[i][j] += f[i - 1][k] - f[i - 2][j]\n",
    "                if i > 3: f[i][j] += f[i - 2][j]\n",
    "                f[i][j] %= MOD\n",
    "        return sum(f[n]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if(n==1):return 6\n",
    "        if(n==2):return 22\n",
    "        f=[[0]*9 for i in range(n+1)]\n",
    "        f[1]=[2,0,2,0,0,0,0,0,0]\n",
    "        f[2]=[4,2,2,4,2,2,2,2,2]\n",
    "        mod=1000000007\n",
    "        # 12 13 16 21 23 31 32 61 15\n",
    "        # 14 53 56 25 43 35 34 65 51\n",
    "        # 52       41\n",
    "        # 54       45\n",
    "        for i in range(3,n+1):\n",
    "            f[i][0]=(f[i-1][3]+2*f[i-1][5]+2*f[i-2][2]+2*f[i-1][8])%mod\n",
    "            f[i][1]=(f[i-1][3]+f[i-2][2]+f[i-1][8])%mod\n",
    "            f[i][2]=(f[i-1][3]+f[i-1][5]+f[i-1][8])%mod\n",
    "            f[i][3]=(f[i-1][0]+2*f[i-1][6])%mod\n",
    "            # f[i][4]=f[i-1][0]\n",
    "            f[i][5]=(f[i-1][1]+2*f[i-2][0])%mod\n",
    "            f[i][6]=(f[i-1][1]*2+f[i-2][0])%mod\n",
    "            # f[i][7]=f[i-1][2]\n",
    "            f[i][8]=(f[i-1][3]+f[i-1][5]+f[i-2][2])%mod\n",
    "        return (sum(f[n])+f[n-1][0]+f[n-1][2])%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        gcd = [[0] * 7 for _ in range(7)]\n",
    "        for i in range(1, 7):\n",
    "            for j in range(1, 7):\n",
    "                gcd[i][j] = math.gcd(i, j)\n",
    "        f = [[0] * 7 for _ in range(n)]\n",
    "        mod = 1000000007\n",
    "        for i in range(1, 7):\n",
    "            f[0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            if i - 3 >= 0:\n",
    "                for j in range(1, 7):\n",
    "                    f[i - 1][j] += f[i - 3][j]\n",
    "            for j1 in range(1, 7):\n",
    "                for j2 in range(1, 7):\n",
    "                    if j1 == j2 or gcd[j1][j2] != 1:\n",
    "                        continue\n",
    "                    f[i][j1] += f[i - 1][j2]\n",
    "                    if i - 2 >= 0:\n",
    "                        f[i][j1] -= f[i - 2][j1]\n",
    "                f[i][j1] %= mod\n",
    "        return sum(f[n - 1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4\n",
    "f = [[[0] * 6 for _ in range(6)] for _ in range(MX + 1)]\n",
    "f[2] = [[int(j != i and gcd(j + 1, i + 1) == 1) for j in range(6)] for i in range(6)]\n",
    "for i in range(2, MX):\n",
    "    for j in range(6):\n",
    "        for last in range(6):\n",
    "            if last != j and gcd(last + 1, j + 1) == 1:\n",
    "                f[i + 1][j][last] = sum(f[i][last][last2] for last2 in range(6) if last2 != j) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return sum(sum(row) for row in f[n]) % MOD if n > 1 else 6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4\n",
    "f = [[[0] * 6 for _ in range(6)] for _ in range(MX + 1)]\n",
    "f[2] = [[int(j != i and gcd(j + 1, i + 1) == 1) for j in range(6)] for i in range(6)]\n",
    "for i in range(2, MX):\n",
    "    for j in range(6):\n",
    "        for last in range(6):\n",
    "            if last != j and gcd(last + 1, j + 1) == 1:\n",
    "                f[i + 1][j][last] = sum(f[i][last][last2] for last2 in range(6) if last2 != j) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return sum(sum(row) for row in f[n]) % MOD if n > 1 else 6\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4\n",
    "f = [[[0] * 6 for _ in range(6)] for _ in range(MX + 1)]\n",
    "f[2] = [[int(j != i and gcd(j + 1, i + 1) == 1) for j in range(6)] for i in range(6)]\n",
    "for i in range(2, MX):\n",
    "    for j in range(6):\n",
    "        for last in range(6):\n",
    "            if last != j and gcd(last + 1, j + 1) == 1:\n",
    "                f[i + 1][j][last] = sum(f[i][last][last2] for last2 in range(6) if last2 != j) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return sum(sum(row) for row in f[n]) % MOD if n > 1 else 6\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "三维dp\n",
    "定义 f[i][last][last2] 表示序列长度为 i，最后一个元素是 last，\n",
    "倒数第二个元素是 last2 的序列数目。\n",
    "'''\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4\n",
    "f = [[[0] * 6 for _ in range(6)] for _ in range(MX + 1)]\n",
    "f[2] = [[int(j != i and gcd(j + 1, i + 1) == 1) for j in range(6)] for i in range(6)]\n",
    "for i in range(2, MX):\n",
    "    for j in range(6):\n",
    "        for last in range(6):\n",
    "            if last != j and gcd(last + 1, j + 1) == 1:\n",
    "                f[i + 1][j][last] = sum(f[i][last][last2] for last2 in range(6) if last2 != j) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return sum(sum(row) for row in f[n]) % MOD if n > 1 else 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        f = [[[0] * 6 for _ in range(6)] for _ in range(n)]\n",
    "        if n < 3:\n",
    "            return [6, 22][n - 1]\n",
    "        for i in range(6):\n",
    "            for j in range(6):\n",
    "                if i != j and gcd(i + 1, j + 1) == 1:\n",
    "                    f[1][i][j] = 1\n",
    "        # print(sum([sum(f[1][i]) for i in range(6)]), f[1])\n",
    "        mod = (10 ** 9 + 7)\n",
    "        for i in range(2, n):\n",
    "            for j in range(6):\n",
    "                for k in range(6):\n",
    "                    for m in range(6):\n",
    "                        if gcd(j+ 1, k + 1) == 1 and m != k and j != k:\n",
    "                            f[i][j][k] += f[i - 1][m][j]\n",
    "                            f[i][j][k] %= mod\n",
    "        ans = 0\n",
    "        for i in range(6):\n",
    "            for j in range(6):\n",
    "                ans += f[-1][i][j]\n",
    "        return ans % (mod)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 4\n",
    "f = [[[0] * 6 for _ in range(6)] for _ in range(MX + 1)]\n",
    "f[2] = [[int(j != i and gcd(j + 1, i + 1) == 1) for j in range(6)] for i in range(6)]\n",
    "for i in range(2, MX):\n",
    "    for j in range(6):\n",
    "        for last in range(6):\n",
    "            if last != j and gcd(last + 1, j + 1) == 1:\n",
    "                f[i + 1][j][last] = sum(f[i][last][last2] for last2 in range(6) if last2 != j) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return sum(sum(row) for row in f[n]) % MOD if n > 1 else 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        if n==1: return 6\n",
    "        dp = [[[0]*6 for _ in range(6)] for _ in range(n)]\n",
    "        for i in range(6):\n",
    "            for j in range(6):\n",
    "                dp[1][i][j] = (1 if math.gcd(i+1,j+1)==1 and i!=j else 0)\n",
    "        for x in range(2,n):\n",
    "            for i in range(6):\n",
    "                for j in range(6):\n",
    "                    for k in range(6):\n",
    "                        if math.gcd(i+1,j+1)==1 and i!=j and i!=k:\n",
    "                            dp[x][i][j] = (dp[x][i][j] + dp[x-1][j][k])%MOD\n",
    "            pass\n",
    "        return sum([sum(s) for s in dp[-1]])%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 6\n",
    "        mod = 10 ** 9 + 7\n",
    "        # dp[i][j][k]当前骰子第i次,且前两次投的是j,k\n",
    "        dp = [[[0 for _ in range(7)] for _ in range(7)] for _ in range(n)]\n",
    "        for i in range(1,7):\n",
    "            dp[0][i][0] = 1\n",
    "        e = [[] for _ in range(7)]\n",
    "        for i in range(1,7):\n",
    "            for j in range(i + 1,7):\n",
    "                if math.gcd(i,j) == 1:\n",
    "                    e[i].append(j)\n",
    "                    e[j].append(i)\n",
    "        # 两轮\n",
    "        for i in range(1,7):\n",
    "            for j in e[i]:\n",
    "                dp[1][i][j] += dp[0][j][0]\n",
    "                \n",
    "        for i in range(2,n):\n",
    "            for j in range(1,7):\n",
    "                for k in e[j]:\n",
    "                    for lst in e[k]:\n",
    "                        if lst != j:\n",
    "                            dp[i][j][k] += dp[i - 1][k][lst]\n",
    "                            dp[i][j][k] %= mod\n",
    "                    # j,k ,k,?\n",
    "        ans = 0\n",
    "        for i in range(1,7):\n",
    "            for j in range(1,7):\n",
    "                ans += dp[-1][i][j]\n",
    "                ans %= mod\n",
    "        return ans % mod\n",
    "                    \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 6\n",
    "        mod = 10 ** 9 + 7\n",
    "        # dp[i][j][k]当前骰子第i次,且前两次投的是j,k\n",
    "        dp = [[[0 for _ in range(7)] for _ in range(7)] for _ in range(n)]\n",
    "        for i in range(1,7):\n",
    "            dp[0][i][0] = 1\n",
    "        e = [[] for _ in range(7)]\n",
    "        for i in range(1,7):\n",
    "            for j in range(i + 1,7):\n",
    "                if math.gcd(i,j) == 1:\n",
    "                    e[i].append(j)\n",
    "                    e[j].append(i)\n",
    "        # 两轮\n",
    "        for i in range(1,7):\n",
    "            for j in e[i]:\n",
    "                dp[1][i][j] += dp[0][j][0]\n",
    "                \n",
    "        for i in range(2,n):\n",
    "            for j in range(1,7):\n",
    "                for k in e[j]:\n",
    "                    for lst in e[k]:\n",
    "                        if lst != j:\n",
    "                            dp[i][j][k] += dp[i - 1][k][lst]\n",
    "                            dp[i][j][k] %= mod\n",
    "                    # j,k ,k,?\n",
    "        ans = 0\n",
    "        for i in range(1,7):\n",
    "            for j in range(1,7):\n",
    "                ans += dp[-1][i][j]\n",
    "                ans %= mod\n",
    "        return ans % mod\n",
    "                    \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        f = [[[0] * 7 for _ in range(7)] for i in range(n)]\n",
    "        gcd = [[0] * 7 for _ in range(7)]\n",
    "        gcd[2][4] = gcd[2][6] = gcd[4][2] = gcd[6][2] = 1\n",
    "        gcd[3][6] = gcd[6][3] = 1\n",
    "        gcd[4][6] = gcd[6][4] = 1\n",
    "        ok = []\n",
    "        M = 10 ** 9 + 7\n",
    "        for i in range(1, 7):\n",
    "            for j in range(i + 1, 7):\n",
    "                if i == j or gcd[i][j]:\n",
    "                    continue\n",
    "                ok.append((i, j))\n",
    "                ok.append((j, i))\n",
    "                # print(i, j)\n",
    "                f[0][i][j] = f[0][j][i] = 1\n",
    "        for i in range(1, n - 1):\n",
    "            for a, b in ok:\n",
    "                for c in range(1, 7):\n",
    "                    if c == a or c == b or gcd[b][c]:\n",
    "                        continue\n",
    "                    f[i][b][c] += f[i - 1][a][b]\n",
    "                    f[i][b][c] %= M               \n",
    "        return sum([sum(row) for row in f[n - 2]]) % M if n > 1 else 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n:int)->int:\n",
    "        MOD = 10**9+7\n",
    "        g = [[1] * 7 for _ in range(7)]\n",
    "        for i in range(7):\n",
    "            for j in range(7):\n",
    "                g[i][j] = gcd(i+1, j+1)\n",
    "        dp = [[[1] * 7 for _ in range(7)] for _ in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(7):\n",
    "                for k in range(7):\n",
    "                    ans = 0\n",
    "                    for m in range(6):\n",
    "                        if m!=j and m!=k and g[m][k]==1:\n",
    "                            ans += dp[i+1][k][m]\n",
    "                    dp[i][j][k] = ans % MOD\n",
    "        return dp[0][6][6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n:int)->int:\n",
    "        MOD = 10**9+7\n",
    "        g = [[1] * 7 for _ in range(7)]\n",
    "        for i in range(7):\n",
    "            for j in range(7):\n",
    "                g[i][j] = gcd(i+1, j+1)\n",
    "        dp = [[[1] * 7 for _ in range(7)] for _ in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(7):\n",
    "                for k in range(7):\n",
    "                    ans = 0\n",
    "                    for m in range(6):\n",
    "                        if m!=j and m!=k and g[m][k]==1:\n",
    "                            ans += dp[i+1][k][m]\n",
    "                    dp[i][j][k] = ans % MOD\n",
    "        return dp[0][6][6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "class Solution:\n",
    "    def distinctSequences(self, n:int)->int:\n",
    "        MOD = 10**9+7\n",
    "        g = [[1] * 7 for _ in range(7)]\n",
    "        for i in range(7):\n",
    "            for j in range(7):\n",
    "                g[i][j] = gcd(i+1, j+1)\n",
    "        dp = [[[1] * 7 for _ in range(7)] for _ in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(7):\n",
    "                for k in range(7):\n",
    "                    ans = 0\n",
    "                    for m in range(6):\n",
    "                        if m!=j and m!=k and g[m][k]==1:\n",
    "                            ans += dp[i+1][k][m]\n",
    "                    dp[i][j][k] = ans % MOD\n",
    "        return dp[0][6][6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\r\n",
    "def f(n: int, last: int, last2: int) -> int:\r\n",
    "    if n == 0: return 1\r\n",
    "    res = 0\r\n",
    "    for j in range(1, 7):\r\n",
    "        if j != last and j != last2 and gcd(j, last) == 1:\r\n",
    "            res += f(n - 1, j, last)\r\n",
    "    return res % (10 ** 9 + 7)\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def distinctSequences(self, n: int) -> int:\r\n",
    "        return f(n, 7, 7)  # 7 与 [1,6] 内的数字都不同且互质"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def f(n: int, last: int, last2: int) -> int:\n",
    "    if n == 0: return 1\n",
    "    res = 0\n",
    "    for j in range(1, 7):\n",
    "        if j != last and j != last2 and gcd(j, last) == 1:\n",
    "            res += f(n - 1, j, last)\n",
    "    return res % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return f(n, 7, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def dfs(n: int, last1: int, last2: int) -> int:\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    ans = 0\n",
    "    for cur in range(1, 7):\n",
    "        if cur != last1 and cur != last2 and gcd(cur, last1) == 1:\n",
    "            ans += dfs(n - 1, cur, last1)\n",
    "    return ans % mod\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return dfs(n, 7, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "@cache\n",
    "def dfs(n,last,last2):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    ans=0\n",
    "    for i in range(1,7):\n",
    "        if i!=last and i!=last2 and gcd(i,last)==1:\n",
    "            ans+=dfs(n-1,i,last)\n",
    "    return ans%MOD\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return dfs(n,7,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "@cache\n",
    "def dfs(n,last,last2):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    ans=0\n",
    "    for i in range(1,7):\n",
    "        if i!=last and i!=last2 and gcd(i,last)==1:\n",
    "            ans+=dfs(n-1,i,last)\n",
    "    return ans%MOD\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return dfs(n,7,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "@cache\n",
    "def dfs(n,last,last2):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    ans=0\n",
    "    for i in range(1,7):\n",
    "        if i!=last and i!=last2 and gcd(i,last)==1:\n",
    "            ans+=dfs(n-1,i,last)\n",
    "    return ans%MOD\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return dfs(n,7,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        mod = 10**9 + 7 \n",
    "        s = {j:[k for k in range(1, 7) if math.gcd(j, k)==1] for j in range(1, 7)} \n",
    "        s[0] = [j for j in range(1, 7)]\n",
    "        @cache \n",
    "        def f(j, p1, p2):\n",
    "            if j==0:\n",
    "                return 1 \n",
    "            else:\n",
    "                ans = 0 \n",
    "                for i in s[p2]:\n",
    "                    if (i!=p1) and (i!=p2):\n",
    "                        ans += f(j-1, p2, i) \n",
    "                return ans%mod \n",
    "        return f(n, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        pos = [[True]*6 for _ in range(6)]\n",
    "        for i in range(6):\n",
    "            for j in range(6):\n",
    "                if math.gcd(i+1,j+1) != 1:\n",
    "                    pos[i][j] = False\n",
    "\n",
    "        dp = [[0]*6 for _ in range(n)]\n",
    "        dp[0] = [1]*6\n",
    "        for idx in range(1, n):\n",
    "            for i in range(6): # 尝试在当前位置放i+1\n",
    "                for j in range(6): \n",
    "                    # 假如前一个数字是j+1，则判断是否可以接上\n",
    "                    if pos[i][j] and i != j:\n",
    "                        dp[idx][i] += dp[idx-1][j]\n",
    "                        # 接上之后，当前位和前前一位不能相等\n",
    "                        if idx-2 >= 0:\n",
    "                            dp[idx][i] -= dp[idx-2][i]\n",
    "                if idx-3 >= 0:\n",
    "                    dp[idx][i] += dp[idx-2][i]\n",
    "        # print(dp)\n",
    "        return sum(dp[-1])%(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "gcd = lru_cache(gcd)\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, pre: Tuple[int, int]) -> int:\n",
    "            if index == n:\n",
    "                return 1\n",
    "\n",
    "            res = 0\n",
    "            for cur in set(range(1, 7)) - set(pre):\n",
    "                if pre[-1] == 0 or gcd(pre[-1], cur) == 1:\n",
    "                    res += dfs(index + 1, pre[1:] + (cur,))\n",
    "                    res %= MOD\n",
    "            return res\n",
    "\n",
    "        res = dfs(0, tuple([0, 0]))\n",
    "        dfs.cache_clear()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "gcd = lru_cache(gcd)\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, pre: Tuple[int, int]) -> int:\n",
    "            if index == n:\n",
    "                return 1\n",
    "\n",
    "            res = 0\n",
    "            for cur in set(range(1, 7)) - set(pre):\n",
    "                if pre[-1] == 0 or gcd(pre[-1], cur) == 1:\n",
    "                    res += dfs(index + 1, pre[1:] + (cur,))\n",
    "                    res %= MOD\n",
    "            return res\n",
    "\n",
    "        res = dfs(0, tuple([0, 0]))\n",
    "        dfs.cache_clear()\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def dfs(n: int, last: int, last2: int) -> int:\n",
    "    if n == 0: # 已经走到终点了\n",
    "        return 1 # 返回一个合法方案\n",
    "\n",
    "    res = 0\n",
    "    for cur in range(1, 7):\n",
    "        if cur != last and cur != last2 and gcd(cur, last) == 1:\n",
    "            res += dfs(n-1, cur, last)\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return dfs(n, 7, 7) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def dfs(n: int, last: int, last2: int) -> int:\n",
    "    if n == 0: # 已经走到终点了\n",
    "        return 1 # 返回一个合法方案\n",
    "\n",
    "    res = 0\n",
    "    for cur in range(1, 7):\n",
    "        if cur != last and cur != last2 and gcd(cur, last) == 1:\n",
    "            res += dfs(n-1, cur, last)\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return dfs(n, 7, 7) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "@cache\n",
    "def dfs(n: int, last: int, last2: int) -> int:\n",
    "    if n == 0: # 已经走到终点了\n",
    "        return 1 # 返回一个合法方案\n",
    "\n",
    "    res = 0\n",
    "    for cur in range(1, 7):\n",
    "        if cur != last and cur != last2 and gcd(cur, last) == 1:\n",
    "            res += dfs(n-1, cur, last)\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        return dfs(n, 7, 7) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        gcd = {1:{2,3,4,5,6}, 2:{1,3,5}, 3:{1,2,4,5}, 4:{1,3,5}, 5:{1,2,3,4,6}, 6:{1,5}}\n",
    "\n",
    "        @cache\n",
    "        def helper(a, b, i):\n",
    "            if i == n:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for candidate in gcd[b]:\n",
    "                if candidate == a:\n",
    "                    continue\n",
    "                \n",
    "                res += helper(b, candidate, i + 1)\n",
    "\n",
    "            return res\n",
    "        \n",
    "        return sum(helper(0, i, 1) for i in range(1, 7)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        #copy\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i,pre,prepre):\n",
    "            if i == n :\n",
    "                return 1\n",
    "            \n",
    "            ans = 0\n",
    "            for j in range(1,7):\n",
    "                if j != pre and j != prepre and gcd(j,pre) ==1:\n",
    "                    ans = (ans +dfs(i+1,j,pre))%MOD\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,7,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9+7\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @cache \n",
    "        def f(indx,x,y): #第indx为x且indx+1不为y的序列数\n",
    "            if indx == n-1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(1,7):\n",
    "                if i == x or gcd(i,x)>1 or i==y:\n",
    "                    continue\n",
    "                res += f(indx+1, i, x)\n",
    "            return res%mod\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1,7):\n",
    "            res += f(0,i,-1)\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(n: int, last: int, last2: int) -> int:\n",
    "            if n == 0: \n",
    "                return 1\n",
    "            res = 0\n",
    "            for j in range(1, 7):\n",
    "                if j != last and j != last2 and gcd(j, last) == 1:\n",
    "                    res += f(n - 1, j, last)\n",
    "            return res % (10 ** 9 + 7)\n",
    "        return f(n, 7, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,pre,pre_last):\n",
    "            if i==n:\n",
    "                return 1\n",
    "            res=0\n",
    "            for num in range(1,7):\n",
    "                if (not pre or gcd(num,pre)==1) and num!=pre and num!=pre_last:\n",
    "                    res+=dfs(i+1,num,pre)\n",
    "            return res%MOD\n",
    "        return dfs(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,pre,pre_last):\n",
    "            if i==n:\n",
    "                return 1\n",
    "            res=0\n",
    "            for num in range(1,7):\n",
    "                if num!=pre and num!=pre_last and gcd(num,pre)==1:\n",
    "                    res=(res+dfs(i+1,num,pre))%MOD\n",
    "            return res%MOD\n",
    "        return dfs(0,7,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "                    \n",
    "            \n",
    "                    @cache\n",
    "                    def dfs(i,pre,last):\n",
    "                        if i == n:\n",
    "                            return 1\n",
    "                        ans = 0\n",
    "                        for j in range(1,7):\n",
    "                            if pre == -1 or (j  != pre and gcd(pre,j) == 1 and j != last):\n",
    "                                ans += dfs(i+1,j,pre)\n",
    "                                ans%= (10 ** 9 + 7)\n",
    "                        return ans\n",
    "                    \n",
    "                    return dfs(0,-1,-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(n: int, last1: int, last2: int) -> int:\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for cur in range(1, 7):\n",
    "                if cur != last1 and cur != last2 and gcd(cur, last1) == 1:\n",
    "                    ans += dfs(n - 1, cur, last1)\n",
    "            return ans % mod\n",
    "        return dfs(n, 7, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,pre,pre_last):\n",
    "            if i==n:\n",
    "                return 1\n",
    "            res=0\n",
    "            for num in range(1,7):\n",
    "                if num!=pre and num!=pre_last and gcd(num,pre)==1:\n",
    "                    res+=dfs(i+1,num,pre)\n",
    "            return res%MOD\n",
    "        return dfs(0,7,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,pre,pre_last):\n",
    "            if i==n:\n",
    "                return 1\n",
    "            res=0\n",
    "            for num in range(1,7):\n",
    "                if (not pre or gcd(num,pre)==1) and num!=pre and num!=pre_last:\n",
    "                    res=(res+dfs(i+1,num,pre))%MOD\n",
    "            return res%MOD\n",
    "        return dfs(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distinctSequences(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(j, k, r):\n",
    "            if r == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for a in range(1, 7):\n",
    "                if gcd(a, k) == 1 and a != j and a != k:\n",
    "                    res += dfs(k, a, r - 1)\n",
    "            return res % 1000000007\n",
    "        return dfs(0, -1, n)\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
